class Solution:
    def mySqrt(self, x: int) -> int:
        if x <= 1:
            return x
        min_res, max_res = 1, x - 1
        while True:
            i = (min_res + max_res) // 2
            if i ** 2 == x or (i ** 2 < x < (i + 1) ** 2):
                return i
            elif i ** 2 > x:
                max_res = i
            else:
                min_res = i


a = Solution()
print(a.mySqrt(1))
print(a.mySqrt(2))
print(a.mySqrt(3))
print(a.mySqrt(4))
print(a.mySqrt(5))
print(a.mySqrt(6))
print(a.mySqrt(7))
print(a.mySqrt(8))
print(a.mySqrt(9))
print(a.mySqrt(9000))